package 背包问题;

import java.util.Scanner;

/**
 * http://www.jeepxie.net/article/38300.html
 * 慕课网算法视频第九章第五节有原理解析
 * 拉到最下面，看第二个循环解法
 *
 *
 * 问题描述：
 *  给定 N 件物品和一个容量为 V 的背包。放入第i件物品耗费的空间为 C[i] ，得到的价值是 W[i] 。
 *  问：哪些物品装入背包可使价值总和最大？最大是多少？
 */
public class 循环方式的01背包问题解法 {
    // N表示物体的个数，C表示背包的容量
    int N, C;
    // 存储每个物体的重量，下标从1开始
    private int[] weight;
    // 存储每个物体的收益，下标从1开始
    private int[] value;
    // 二维数组，用来保存每种状态下的最大收益（也就是状态转移方程）
    private int[][] F;

    /**
     * 使用非递归方式，求解 F[0 .. N][0 .. C]，即 for 循环从下至上求解
     */
    public void ZeroOnePackNonRecursive() {
        //对二维数组F进行初始化
        for (int j = 0; j <= C; j++) {
            F[0][j] = 0;
        }

        // 注意边界问题，i是从1开始的，j是从0开始的
        // 因为 F[i - 1][j]中 i 要减 1
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= C; j++) {
                // 如果容量为 j 的背包放得下第 i 个物体
                if (j >= weight[i]) {
                    F[i][j] = Math.max(F[i - 1][j - weight[i]] + value[i], F[i - 1][j]);
                } else {
                    //放不下，只能选择不放第i个物体
                    F[i][j] = F[i - 1][j];
                }
            }
        }

        //打印所有结果，我们要求的是F[N][C]
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= C; j++) {
                System.out.print(F[i][j] + " ");
            }
            System.out.println();
        }
    }


    /**
     * 求解F[n][m]这个最优值具体选取哪几样物品能获得最大价值，但只会输出一种情况
     *
     * @param n 表示前n个物体，n <= N
     * @param v 表示背包的容量，v <= C
     */
    public void printResult(int n, int v) {
        boolean[] isAdd = new boolean[n + 1];

        for (int i = n; i >= 1; i--) {
            if (F[i][v] == F[i - 1][v])
                isAdd[i] = false;
            else {
                isAdd[i] = true;
                v -= weight[i];
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(isAdd[i] + " ");
        }
        System.out.println();
    }

    /**
     * 输入格式：
     * 5 10
     * 2 2 6 5 4
     * 6 3 5 4 6
     * result: 15
     * 第一行是物体个数、背包总空间；
     * 第二行是每个物体的空间；
     * 第三行是每个物体的收益。
     */
    public void init() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        C = sc.nextInt();

        //下标从1开始，表示第1个物品
        weight = new int[N + 1];
        value = new int[N + 1];
        //注意是 N + 1，因为需要一个初始状态F[0][0]，表示前0个物品放进空间为0的背包的最大收益
        F = new int[N + 1][C + 1];

        for (int i = 1; i <= N; i++) {
            weight[i] = sc.nextInt();
        }

        for (int i = 1; i <= N; i++) {
            value[i] = sc.nextInt();
        }
    }

    public static void main(String[] args) {
//        循环方式的01背包问题解法 zop = new 循环方式的01背包问题解法();
//        zop.init();
//        zop.ZeroOnePackNonRecursive();
//        zop.printResult(zop.N, zop.C);

        int[] weight = {2, 2, 6, 5, 4};
        int[] value = {6, 3, 5, 4, 6};
        int c = 10;
        System.out.println(knapsack01(weight, value, c)); // 15

    }


    /**
     * 慕课网教学算法
     * <p>
     * 以下代码按照此图 https://s2.ax1x.com/2020/02/03/10gc2d.png
     * 编写，具体过程参考视频教学
     *
     * @param weight 待选物品的重量
     * @param value  待选物品对应的价值
     * @param c      背包可以承受的总容量
     * @return 可以装下的物品的最大价值
     */
    public static int knapsack01(int[] weight, int[] value, int c) {
        int n = weight.length;
        // 如果没有物品可选，最大价值就是0
        if (n == 0)
            return 0;

        // 注意：在图示中，物品从 0 开始编号，则物品 0 占据一个位置
        // 同理，容量 C 也是从 0 开始编号的，因此 [0, C+1) 就表示容量为 C 的背包
        int[][] dp = new int[n][c + 1];


        /*
        脑海里开始浮现视频中这张图的解析过程，一边回想一边写算法
         */


        // 先处理表格中第一行
        // 从背包容量为0开始到背包满了。检查第0号物品能否放入背包
        for (int j = 0; j <= c; j++) {
            dp[0][j] = (j >= weight[0]) ? value[0] : 0;
        }

        // 然后开始从表格的第二行开始处理
        for (int i = 1; i < n; i++) { // 注意这里不是 <=n，因为i是从0开始的
            // 然后也是从背包容量为0开始检查当前i号物品能否存入背包
            for (int j = 0; j <= c; j++) {
                // 从第二行开始的计算要依赖于之前的计算结果

                dp[i][j] = dp[i - 1][j];//表示不把第i个物品放入背包，任然使用第i-1号物品的最大价值

                // 若准备尝试把第i个物品存入背包的话，得先保证能放进去
                if (j >= weight[i]) {
                    // 然后计算【放入后获得的价值最大值】与上面【不放进去的价值】的最大值
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        /*
        之前设置的dp大小为：[n][c + 1]
        那是因为物品是从0开始编号的，3个物品就是0,1,2
        但是容量是从0开始模拟的，所以容量为5的时候其实要从0开始遍历，所以数组的大小开辟成[n][c + 1]
         */

        // 最大价值就存储在 dp 的最后一格
        return dp[n - 1][c];
    }
}
